#include <vector>
#include <queue>
#include <iostream>

using namespace std;

/*
313. 超级丑数
已解答
中等
相关标签
相关企业
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

 

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
 
提示：

1 <= n <= 105
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列
*/

// 法一
class Node {
public:
    int Prime; // 质数
    int Index; // 当前质数对应的索引位置
    int Val;   // 当前节点的值，即Prime * vec[Index]

    // 构造函数
    Node(int prime, int index, int val) {
        Prime = prime;
        Index = index;
        Val = val;
    }
};

// 自定义的比较器类，重载运算符，用于在优先队列中进行排序
class Comparator {
public:
    bool operator()(const Node& a, const Node& b) {
        // 比较两个Node的Val值，返回Val较大的那个作为优先队列的优先级
        return a.Val > b.Val;
    }
};

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // 初始化一个数组 vec，保存丑数，初始值是1（丑数序列的第一个数字为1）
        vector<int> vec;
        vec.push_back(1);
        // 优先队列 queue
        // 用来维护当前的最小值。根据题目要求，每次从所有质因数的候选丑数中取出最小的作为下一个丑数。
        priority_queue<Node, vector<Node>, Comparator> queue;
        for (int i = 0; i < primes.size(); ++i) {
            // 将每个质数对应的第一个丑数（即质数本身）加入队列
            queue.push(Node(primes[i], 0, primes[i]));
        }
        // 生成超级丑数，直到我们获得第n个超级丑数
        while (vec.size() < n) {
            // 取出当前队列中最小的元素
            Node cur = queue.top();
            queue.pop();
            // 如果当前的值大于上一个丑数，说明这是下一个丑数，将其添加到 vec 中
            if (vec.back() < cur.Val) {
                vec.push_back(cur.Val);
            }
            // 更新队列中的元素：每个质数的下一个丑数是当前质数乘以 vec
            // 数组中对应索引位置的丑数
            queue.push(Node(cur.Prime, cur.Index + 1, cur.Prime * vec[cur.Index + 1]));
        }
        // 返回第n个超级丑数
        return vec[n - 1];
    }
};

int main() {
    Solution solution;
    vector<int> primes = {2, 7, 13, 19};
    int n = 12;
    cout << solution.nthSuperUglyNumber(n, primes) << endl; // 输出 32
    return 0;
}
    
// 法二
class Solution {
    public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // 初始化指针数组，用于跟踪每个质数当前的乘积位置
        vector<int> pointers(primes.size(), 0);
        // dp数组用来存储超级丑数，dp[i]表示第i+1个超级丑数
        vector<long long> dp(n, 0);
        // 第一个超级丑数是1
        dp[0] = 1;
        // 优先队列pq，用来存储键值对，键是当前丑数的值，值是对应的质数的索引
        // 使用greater<pair<long long, int>>让优先队列按值从小到大排序
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        // 初始化优先队列，将每个质数的第一个丑数（质数本身）加入队列
        for (int i = 0; i < primes.size(); i++) {
            pq.push({primes[i], i});
        }
        // 从第二个超级丑数开始，计算直到第n个超级丑数
        for (int i = 1; i < n; ++i) {
            // 取出队列中的最小值作为当前的丑数（即dp[i]）
            dp[i] = pq.top().first;
            // 当队列中有多个相同值的最小丑数时，更新每个质数的指针，并将新的丑数入队
            while (!pq.empty() && pq.top().first == dp[i]) {
                // 获取队列中当前最小丑数对应的质数的索引
                int index = pq.top().second;
                pq.pop();
                // 更新对应质数的指针，指向下一个可能的丑数
                pointers[index]++;
                // 将新的丑数（当前指针位置的值乘以对应的质数）加入队列
                pq.push({dp[pointers[index]] * primes[index], index});
            }
        }
        // 返回第n个超级丑数
        return dp[n - 1];
    }
};
    